package com.lee.algorithm.unionfind;

/***
 * @description: 岛问题
 *      一个矩阵中只有0和1两种值，每个位置都可以和自己的上、下、左、右四个位置相连
 *      如果有一片1连在一起，这个部分叫做一个岛，求一个矩阵中有多少个岛
 *      举例
 *          001010
 *          111010
 *          100100
 *          000000
 *      这个矩阵中有三个岛(左侧椅子形状、右侧上下两个1、中间单独的那个1)
 *
 *      从上到下、从左到右，逐个遍历找1，一旦找到1就开始进行感染（infect），将该1的上下左右的1都感染成2
 *      感染一次就说明找到1个岛
 * @author 青石路
 * @date 2022/1/3 19:36
 */
public class Islands {

    public static int countIslands(int[][] matrix) {
        if (matrix == null || matrix[0] == null) {
            return 0;
        }
        int rows = matrix.length;
        int columns = matrix[0].length;
        int counts = 0;
        for (int i = 0; i < rows; i++) {
            for (int j = 0; j < columns; j++) {
                if (matrix[i][j] == 1) {
                    counts ++;
                    infect(matrix, i, j, rows, columns);
                }
            }
        }
        return counts;
    }

    /**
     * 感染
     * @param matrix 矩阵
     * @param i 当前行
     * @param j 当前列
     * @param rows 矩阵的行数
     * @param columns 矩阵的列数
     */
    public static void infect(int[][] matrix, int i, int j, int rows, int columns) {
        if (i<0 || i>=rows || j<0 || j>=columns || matrix[i][j] != 1) {
            return;
        }

        // i、j 都没越界，并且当前位置是 1
        matrix[i][j] = 2;
        infect(matrix, i - 1, j, rows, columns);     // 当前位置的 上
        infect(matrix, i + 1, j, rows, columns);     // 当前位置的 下
        infect(matrix, i, j - 1, rows, columns);     // 当前位置的 左
        infect(matrix, i ,j + 1, rows, columns);     // 当前位置的 右
    }

    // 如何设计一个并行算法解决这个问题
    // 并查集
    /**
     * 多核 cpu
     * 分块感染，在进行合并
     *
     *
     */
}
